package fun.ticsmyc.question.dp;

import fun.ticsmyc.tools.ArrayTools;
import org.junit.Test;

/**
 * @author Ticsmyc
 * @package fun.ticsmyc.question.dp
 * @date 2021-02-06 17:04
 */
public class 背包 {

    /**
     *  0-1背包
     * @param w 背包容量
     * @param n n个物品
     * @param wt 物品重量
     * @param val 物品价值
     * @return
     */
    public int knapsack0_1(int w, int n,int[] wt,int[] val){

        int[][] dp = new int[n+1][w+1];
        for(int i=1 ;i<=n;++i){
            for(int j=1;j<=w;++j){
                if(j-wt[i-1] <0){
                    //装不下
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-wt[i-1]]+val[i-1]);
                }
            }
        }

        ArrayTools.printArray(dp);
        return dp[n][w];
    }

    /**
     * 状态压缩后的0-1背包
     * @param w
     * @param n
     * @param wt
     * @param val
     * @return
     */
    public int zeroOnePack(int w ,int n, int[] wt ,int[] val){
        int[] dp = new int[w+1];
        for(int i=0;i<n;++i){
            // 从后往前遍历  不然会重复计算
            for(int j=dp.length-1;j>=0;--j){
                if(j - wt[i] >=0){
                    dp[j] = Math.max(dp[j], dp[j-wt[i]]+val[i]);
                }
            }
            ArrayTools.printArray(dp);
        }
        return dp[w-1];
    }

    @Test
    public void test01背包(){
        knapsack0_1(10,5,new int[]{1,2,3,4,5},new int[]{5,4,3,2,1});

        System.out.println();

        zeroOnePack(10,5,new int[]{1,2,3,4,5},new int[]{5,4,3,2,1});
    }

    /**
     * 完全背包 ： 零钱兑换2
     * @param amount
     * @param coins
     * @return
     */
    public int change(int amount, int[] coins) {
        int m = coins.length;

        int[][] dp = new int[m+1][amount+1];
        dp[0][0]=1;
        for(int i=1;i<dp.length;++i){
            for(int j=0;j<dp[0].length;++j){
                if(j - coins[i-1] >=0){
                    dp[i][j] =dp[i-1][j] +dp[i][j-coins[i-1]];
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[m][amount];
    }
}
